package graph;

import java.util.ArrayList;
import java.util.Arrays;

public class GraphDome<T> {
    private ArrayList<T> dataList;  //  图的节点集合
    private int[][] edges;          //图的邻接矩阵
    private Integer numForEdges;    //边的个数
    private boolean[] isVisited;    //定义给数组boolean[], 记录某个结点是否被访问

    //构造器

    public GraphDome(int n) {
        edges = new int[n][n];
        dataList = new ArrayList<>();
        numForEdges = 0;
    }


    /**
     * 获取某节点的第一个邻接点
     * @param nodeIndex 需要获取第一个邻接点的节点下标
     * @return
     */
    public int getFirstNeighbor(int nodeIndex){
        for(int i=0;i<dataList.size();i++){
            if(edges[nodeIndex][i]>0){
                return i;
            }
        }
        return -1;
    }

    /**
     *   根据前一个邻接结点的下标来获取下一个邻接结点
     *
     *
     * @param v1 需要被获取邻接点的节点下标
     * @param v2 已经被获取过的 v1节点的邻接点下标
     *           (v2已经被获取过,现在要获取v1所有邻接点中v2之后的邻接点 (邻接矩阵每行为一个节点所有邻接点) )
     *           A  B  C  D  E
     *        A [0, 1, 0, 0, 0]   该行表示与A邻接的节点有 B
     *        B [1, 0, 1, 1, 1]   该行表示与B邻接的节点有 A,C,D,E   若此时v2为 C节点,则表示B的邻接点A,C都被获取过,现在函数目标为获取到D节点
     *        C [0, 1, 0, 1, 1]
     *        D [0, 1, 1, 0, 0]
     *        E [0, 1, 1, 0, 0]
     * @return
     */
    public int getNextNeighbor(int v1, int v2) {
        for(int j = v2 + 1; j < dataList.size(); j++) {//将指针定位到 v2之后以获取v2后的关系
            if(edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 深度优先遍历图
     * 为不失普遍性遍历操作为打印节点
     * @param isVisited 用以判断节点是否被访问(若与其同下标的节点被访问则变为true)
     * @param i   开始遍历的节点(递归时为当前所在的节点)
     */
    public void dfs(boolean[] isVisited, int i){
        System.out.println(getData(i));   //打印出遍历到的节点
        isVisited[i]=true;                //标记该节点已被遍历


        int w = getFirstNeighbor(i);   //查找节点(i的第一个邻接点)
        while(w != -1){ //说明有邻接点
            if(!isVisited[w]){//若该邻接点没有被访问过
                dfs(isVisited,w);  //步入w节点并进行递归
            }else {//若已经被访问过

                w = getNextNeighbor(i,w);//获取i节点的w节点之后的邻接点 若有则将w置为该节点等待判断是否被访问过
                // 若无则证明该节点之后没有邻接点 表明以i为头的图访问完毕 结束函数
            }
        }
    }



    //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
    public void dfs(){
        isVisited = new boolean[dataList.size()];
        //遍历所有的结点，进行dfs[回溯]
        for(int i = 0; i < getNumOfDataList(); i++) {
            if(!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }

    //图的常用方法

    /**
     *  按邻接矩阵下标获取节点
     * @param n
     * @return
     */
    public T getData(int n){
        return dataList.get(n);
    }

    /**
     * 获取节点个数
     * @return
     */
    public Integer getNumOfDataList(){
        return dataList.size();
    }


    /**
     * 打印邻接矩阵
     */
    public void showEdges(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    /**
     * 添加新的边关系
     * @param v1 节点下标(节点集合中下标)
     * @param v2 节点下标(节点集合中下标)
     */
    public void addedge(Integer v1,Integer v2){
        edges[v1][v2]=1;
        edges[v2][v1]=1;
        numForEdges++;
    }

    /**
     * 添加节点
     * @param dataNode
     */
    public void adddata(T dataNode){
        dataList.add(dataNode);


    }
}
